1. Field of the Invention
The present invention relates to a method of transmitting information within a network.
2. Description of Related Art
To increase the size, speed and scalability of computer systems, computers may be linked together within a network to process information in parallel. Such systems are commonly referred to as parallel processing networks. Parallel processing networks typically have a plurality of microprocessor based components coupled together by busses and associated hardware. Each processor based component functions as a node which can transmit information to other nodes within the network.
The nodes can be arranged as a plurality of interconnected cubes, commonly referred to as a hypercube. Hypercubes require a large number of data links, which increase the size of the system.
The nodes can also be arranged in a two-dimensional array, commonly referred to as a network mesh. FIGS. 1a-d show a method of exchanging information within a mesh that is commonly referred to as the Direct Exchange Algorithm. In the Direct Exchange method, information is exchanged from one node to another node within the same row of the mesh. The process is repeated until the information of one node is transferred to each of the nodes within the row. For example, as shown in FIG. 1a, in the first step, the information from node 1 is transferred to node 3, node 2 transfers information to node 1, node 3 transfers information to node 4 and the information of node 4 is transferred to node 2. The process of exchanging information between nodes is repeated in accordance with the patterns shown in FIGS. 1b, 1c and 1d. The information can then be exchanged between rows and the process is repeated. Although the Direct Exchange Algorithm has a relatively high transmission rate, the number of messages and the start-up time to send the messages from each node rapidly increases with the size of the mesh.
FIGS. 2a-f and 3a-d show other methods of exchanging information within a mesh, commonly referred to as the Binary Exchange Algorithm and the Quadrant Exchange Algorithm, respectively. Both of theses methods utilize a store and forward approach, wherein each node can both receive and forward information transmitted by another node. As shown in FIG. 2a, in the first step of the Binary Exchange method, the nodes in one half of the mesh transmit information to nodes in the other half of the mesh in a horizontal direction. The process is repeated by sending the information from one half of the mesh to the other half of the mesh in a vertical direction, as shown in FIG. 2b. As shown in FIGS. 2c-f, the information is then exchange within quadrants and subquadrants of the mesh.
In the Quadrant Exchange method, information is exchanged within rectangular groups of nodes as shown in FIGS. 3a and 3b. As shown in FIG. 3C, the information is then exchanged within separate quadrants of the mesh. Although both the Binary and Quadrant Exchange methods can be used in large mesh networks, the start-up time and transmission rate are relatively slow. Additionally, the Quadrant method is susceptible to node contention. It would be desirable to provide an algorithm for a mesh network, that was not susceptible to node contention and had a relatively high complete information exchange rate.
The present invention is a method for exchanging information within a mesh network that has an array of nodes defined by four quadrants. The method includes the initial steps of exchanging information from a set of nodes in one quadrant to a set of nodes located in an adjacent quadrant. The exchange of information simultaneously occurs in both a vertical and horizontal direction within the array. Information is then exchanged between nodes within the same quadrant and subquadrants.